﻿#include <iostream>
using namespace std;

const int n = 5;
int color[n] = {0};
int arc[n][n] = {
	0, 1, 0, 0, 0,
	1, 0, 1, 1, 0,
	0, 1, 0, 0, 1,
	0, 1, 0, 0, 1,
	0, 0, 1, 1, 0
};

int ok(int i){							//判断顶点i的着色是否发生冲突
	for(int j = 0; j < n; j++){			//考察其他所有顶点
		if(arc[i][j] == 1 && color[i] == color[j]){
			return 0;
		}
	}
	
	return 1;
}

void colorGraph(){
	int k = 0;
	int flag = 1;						//flag=1表示图中还有尚未涂色的顶点
	while(flag == 1){
		k++; flag = 0;					//取下一种颜色
		for(int i = 0; i < n; i++){
			if(color[i] == 0){
				color[i] = k;			//顶点i涂颜色k
				if(!ok(i)){				//发生冲突，取消涂色
					color[i] = 0;
					flag = 1;
				}
			}
		}
	}
}

int main(){
	colorGraph();
	for (int i = 0; i < n; i++){
		cout << color[i] << " ";
	}

	system("pause");
	return 0;
}